package com.LeeCode;

/**
 * 小张刷题计划
 */

public class CodeLCP012 {
    public static void main(String[] args) {
        int[] nums = {1, 2, 7, 4, 7, 7};
        int m = 2;
        System.out.println(new CodeLCP012().minTime(nums, m));
        System.out.println(new CodeLCP012().check(nums, m, 7));
    }

    public int minTime(int[] time, int m) {
        int n = time.length;
        if (n <= m) return 0;

        int left = 0, right = Integer.MAX_VALUE;
        while (left + 1 < right) {
            int mid = left + (right - left) / 2;
            if (check(time, m, mid))
                right = mid;
            else
                left = mid;
        }
        return right;
    }

    private boolean check(int[] time, int m, int limit) {
        int days = 1, curSum = 0, maxInDay = 0;
        for (int t : time) {
            curSum += t;
            maxInDay = Math.max(maxInDay, t);

            // 跳过一天中的最大值
            if (curSum - maxInDay > limit) {
                days++;
                curSum = t;
                maxInDay = t;
                if (days > m) {
                    return false;
                }
            }
        }
        return days <= m;
    }
}
